A Viterbi decoder performs the Viterbi algorithm which is a "maximum likelihood" decoding algorithm, so as to decode the code symbol which has been encoded in accordance with a convolutional coding scheme. In the Viterbi algorithm, the received code sequence is compared with a plurality of path code sequences, and the path which has the shortest code distance is selected as the maximum likelihood path. The code sequence which corresponds to the maximum likelihood path is produced as a decoded code sequence. Here, the code sequence is constituted by a plurality of code symbols, and each path includes a plurality of branches having predetermined code symbols. The code distance refers to the difference between the received code sequence and the path code sequence.
As described above, Viterbi algorithms are widely used in the field of digital transmission systems such as satellite communication systems, earth network communication systems and mobile communication systems.
The general Viterbi decoder for performing the Viterbi algorithm operation comprises a branch metric, an add-compare-select circuit (hereinafter referred to as an "ACS circuit") and a path memory apparatus. The conventional path memory apparatus of a Viterbi decoder is implemented by comprising a plurality of select memory units arranged in a trellis structure corresponding the convolutional coding scheme, or by comprising a random access memory (RAM) and the peripheral circuits for the operation thereof.
In the former (utilizing the select memory units), however, as the number of code symbols in the code sequence increases, the number of select memory units increases by a geometric progression, resulting in a larger path memory apparatus. Meanwhile, the latter (utilizing the RAM) has an overly complex address generating circuitry, and thereby its realization is very difficult.